package leetcode20211012;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LUYAO
 * Date: 2021-10-12
 * Time: 10:10
 */
public class DFS {
}


//矩阵中路径
class Solution61 {

    //从任意一个地方都有可能开始匹配到,所以要两层for循环每一个char都遍历到
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(dfs(board,words,i,j,0)) return true;
            }
        }
        return false;
    }


    //从当前开始能匹配到
    boolean dfs(char[][] board, char[] word, int i, int j, int k){
        if(i > board.length || i < 0 || j > board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length-1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);

        board[i][j] = word[k];
        return res;

    }
}

//机器人运动范围
class Solution {
    // 棋盘的行列
    int m, n;
    // 记录位置是否被遍历过
    boolean[][] visited;

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        visited = new boolean[m][n];
        return dfs(0, 0, k);
    }

    private int dfs(int i, int j, int k) {
        // i >= m || j >= n是边界条件的判断
        if (i >= m || j >= n
                // visited[i][j]判断这个格子是否被访问过
                || visited[i][j] == true
                // k < sum(i, j)判断当前格子坐标是否满足条件
                || sum(i, j) > k) {
            return 0;
        }
        // 标注这个格子被访问过
        visited[i][j] = true;
        // 沿着当前格子的右边和下边继续访问
        return 1 + dfs(i + 1, j, k)
                + dfs(i, j + 1, k);
    }

    // 计算两个坐标数字的和
    private int sum(int i, int j) {
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i /= 10;
        }
        while (j != 0) {
            sum += j % 10;
            j /= 10;
        }
        return sum;
    }
}
